home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / 0989.ZIP / ESPRESSO.ARC / REDUCE.C < prev    next >
Text File  |  1987-03-13  |  9KB  |  299 lines
  1. /*
  2.     module: reduce.c
  3.     purpose: Perform the Espresso-II reduction step
  4. */
  5.  
  6. #include "espresso.h"
  7.  
  8. static int sccc_level = 0;
  9. static bool toggle = TRUE;
  10.  
  11. /*
  12.     Reduction is a technique used to explore larger regions of the
  13.     optimization space.  We replace each cube of F with a smaller
  14.     cube while still maintaining a cover of the same logic function.
  15.  
  16.     This operation is inherently cube-order dependent.  The heuristic
  17.     of reducing the cubes in order by size is used.
  18.  
  19.     The real workhorse of this section is the routine SCCC which is
  20.     used to find the Smallest Cube Containing the Complement of a cover.
  21.     Reduction as proposed by Espresso-II takes a cube and computes its
  22.     maximal reduction as the intersection between the cube and the
  23.     smallest cube containing the complement of (F u D - {c}) cofactored
  24.     against c.
  25.  
  26.     As usual, the unate-recursive paradigm is used to compute SCCC.
  27.     The SCCC of a unate cover is trivial to compute, and thus we perform
  28.     shannon cofactor expansion attempting to drive the cover to be unate
  29.     as fast as possible.
  30. */
  31. /*
  32.     reduce -- replace each cube in F with its reduction
  33.  
  34.     The reduction of a cube is the smallest cube contained in
  35.     the cube which can replace the cube in the original cover without
  36.     changing the cover.  This can be computed directly.  The problem is
  37.     that the order in which the cubes are reduced can greatly affect the
  38.     final result.
  39. */
  40.  
  41. pcover reduce(F, D)
  42. INOUT pcover F;
  43. IN pcover D;
  44. {
  45.     register pcube last, p, cunder, *FD;
  46.  
  47.     /* Order the cubes into descending order of size */
  48.     sf_active(F);
  49.     F = toggle ? order_reduce(F) : mini_order(F, descend);
  50.     toggle = ! toggle;
  51.  
  52.     /* Try to reduce each cube */
  53.     FD = cube2list(F, D);
  54.     foreach_set(F, last, p) {
  55.         cunder = reduce_cube(FD, p);
  56.         if (! setp_equal(cunder, p)) {
  57.             if (debug & REDUCE)
  58.                 printf("REDUCE: %s to %s\n", pc1(p), pc2(cunder));
  59.             set_copy(p, cunder);
  60.             if (setp_empty(cunder))
  61.                 RESET(p, ACTIVE);
  62.         }
  63.         free_cube(cunder);
  64.     }
  65.     free_cubelist(FD);
  66.  
  67.     /* Delete any cubes of F which reduced to the empty cube */
  68.     F = sf_inactive(F);
  69.     return F;
  70. }
  71.  
  72.  
  73. /* reduce_cube -- find the maximal reduction of a cube */
  74. pcube reduce_cube(FD, p)
  75. IN pcube *FD, p;
  76. {
  77.     pcube cunder;
  78.     cunder = sccc(cofactor(FD, p));
  79.     (void) set_and(cunder, cunder, p);
  80.     RESET(cunder, PRIME);
  81.     SET(cunder, ACTIVE);
  82.     return cunder;
  83. }
  84. /* sccc -- find Smallest Cube Containing the Complement of a cover */
  85. pcube sccc(T)
  86. INOUT pcube *T;         /* T will be disposed of */
  87. {
  88.     pcube r;
  89.     register pcube cl, cr;
  90.     register int best;
  91.  
  92.     if (debug & REDUCE1)
  93.         debug_print(T, "SCCC", sccc_level++);
  94.  
  95.     if (sccc_special_cases(T, &r) == MAYBE) {
  96.         best=binate_split_select(T,cl = new_cube(), cr = new_cube(), REDUCE1);
  97.         r = sccc_merge(
  98.                 sccc(scofactor(T, cl, best)),
  99.                 sccc(scofactor(T, cr, best)), 
  100.                 cl, cr);
  101.         free_cubelist(T);
  102.     }
  103.  
  104.     if (debug & REDUCE1)
  105.         printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r));
  106.     return r;
  107. }
  108.  
  109. pcover order_reduce(T)
  110. IN pcover T;
  111. {
  112.     register pcube p, last, largest = NULL;
  113.     register int bestsize = -1, size, n = cube.num_vars;
  114.     pcube *T1;
  115.  
  116.     if (T->count == 0)
  117.         return T;
  118.  
  119.     /* find largest cube */
  120.     foreach_set(T, last, p)   
  121.         if ((size = set_ord(p)) > bestsize)
  122.             largest = p, bestsize = size;
  123.  
  124.     foreach_set(T, last, p)
  125.         PUTSIZE(p, ((n - cdist(largest,p)) << 7) + min(set_ord(p),127));
  126.  
  127.     T1 = sf_list(T);
  128.     qsort((char *) T1, T->count, sizeof(pset), descend);
  129.     T = sf_unlist(T1, T->count, T->sf_size);
  130.     return T;
  131. }
  132. bool sccc_special_cases(T, result)
  133. INOUT pcube *T;                 /* will be disposed if answer is determined */
  134. OUT pcube *result;              /* returned only if answer determined */
  135. {
  136.     register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0];
  137.  
  138.     /* empty cover => complement is universe => SCCC is universe */
  139.     if (T[2] == NULL) {
  140.         *result = set_save(cube.fullset); 
  141.         goto exit1;
  142.     }
  143.  
  144.     /* row of 1's => complement is empty => SCCC is empty */
  145.     for(T1 = T+2; (p = *T1++) != NULL; )
  146.         if (full_row(p, cof)) {
  147.             *result = new_cube();
  148.             goto exit1;
  149.         }
  150.  
  151.     /* Collect column counts, determine unate variables, etc. */
  152.     massive_count(T);
  153.  
  154.     /* If cover is unate or single cube, apply simple rules to find SCCCU */
  155.     if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) {
  156.         *result = set_save(cube.fullset);
  157.         for(T1 = T+2; (p = *T1++) != NULL; )
  158.             (void) sccc_cube(*result, set_or(temp, p, cof));
  159.         goto exit1;     
  160.     }
  161.  
  162.     /* Check for a cube which can be easily factored */
  163.     set_copy(ceil = new_cube(), cof);
  164.     for(T1 = T+2; (p = *T1++) != NULL; )
  165.         INLINEset_or(ceil, ceil, p);
  166.     if (! setp_equal(ceil, cube.fullset)) {
  167.         *result = sccc_cube(set_save(cube.fullset), ceil);
  168.         if (setp_equal(*result, cube.fullset))
  169.             free_cube(ceil);
  170.         else
  171.             *result=sccc_merge(sccc(cofactor(T,ceil)), set_save(cube.fullset),
  172.                         ceil, *result);
  173.         goto exit1;
  174.     }
  175.     free_cube(ceil);
  176.  
  177.     /* Single active column at this point => tautology => SCCC is empty */
  178.     if (cdata.vars_active == 1) {
  179.         *result = new_cube();
  180.         goto exit1;
  181.     }
  182.  
  183.     /* Not much we can do about it */
  184.     return MAYBE;
  185.  
  186. exit1:
  187.     free_cubelist(T);
  188.     return TRUE;
  189. }
  190. pcube sccc_merge(left, right, cl, cr)
  191. INOUT register pcube left, right;       /* will be disposed of ... */
  192. INOUT register pcube cl, cr;            /* will be disposed of ... */
  193. {
  194.     INLINEset_and(left, left, cl);
  195.     INLINEset_and(right, right, cr);
  196.     INLINEset_or(left, left, right);
  197.     free_cube(right);
  198.     free_cube(cl);
  199.     free_cube(cr);
  200.     return left;
  201. }
  202.  
  203.  
  204. /*
  205.     sccc_cube -- find the smallest cube containing the complement of a cube
  206.  
  207.     It is simple to see that the SCCC is the universe if the cube has more
  208.     than two active variables.  If there is only a single active variable,
  209.     then the SCCC is merely the complement of the cube.  A last special case
  210.     is no active variables, in which case the SCCC is empty.
  211.  
  212.     This is "anded" with the incoming cube result.
  213. */
  214. pcube sccc_cube(result, p)
  215. register pcube result, p;
  216. {
  217.     register pcube temp = cube.temp[0];
  218.     register int var, nactive = 0, active = -1;
  219.  
  220.     for(var = 0; var < cube.num_vars; var++)
  221.         if (! setp_implies(cube.var_mask[var], p))
  222.             if (++nactive > 1)
  223.                 break;
  224.             else 
  225.                 active = var;
  226.  
  227.     if (nactive == 1) {
  228.         INLINEset_and(temp, cube.var_mask[active], p);
  229.         INLINEset_diff(temp, cube.fullset, temp);
  230.         INLINEset_and(result, result, temp);
  231.     }
  232.     return result;
  233. }
  234. /*
  235.     mv_reduce -- perform an "optimal" reduction of the variables which
  236.     we desire to be sparse
  237.  
  238.     This could be done using "reduce" and then saving just the desired
  239.     part of the reduction.  Instead, this version uses IRRED to find
  240.     which cubes of an output are redundant.  Note that this gets around
  241.     the cube-ordering problem.
  242.  
  243.     In normal use, it is expected that the cover is irredundant and
  244.     hence no cubes will be reduced to the empty cube (however, this is
  245.     checked for and such cubes will be deleted)
  246. */
  247.  
  248. pcover mv_reduce(F, D)
  249. pcover F, D;
  250. {
  251.     register int i, var;
  252.     register pcube p, *T1, cof;
  253.     pcube *F1, *D1, *F2, *D2, last;
  254.     cof = new_cube();
  255.  
  256.     F1 = cube1list(F);
  257.     D1 = cube1list(D);
  258.  
  259.     /* loop for each multiple-valued variable */
  260.     for(var = 0; var < cube.num_vars; var++)
  261.         if (cube.sparse[var])
  262.  
  263.         /* loop for each part of the variable */
  264.         for(i = cube.first_part[var]; i <= cube.last_part[var]; i++) {
  265.  
  266.             /* Create the cube to cofactor against */
  267.             set_diff(cof, cube.fullset, cube.var_mask[var]);
  268.             set_insert(cof, i);
  269.             F2 = scofactor(F1, cof, var);
  270.             D2 = scofactor(D1, cof, var);
  271.             irred(F2, D2);
  272.  
  273.             set_copy(cof, cube.fullset);
  274.             set_remove(cof, i);
  275.             for(T1 = F2 + 2; (p = *T1++); )
  276.                 if (! TESTP(p, ACTIVE))
  277.                     if (var == cube.num_vars-1 ||
  278.                          ! setp_implies(cube.var_mask[var], p)) {
  279.                     INLINEset_and(p, p, cof);
  280.                     RESET(p, PRIME);
  281.                 }
  282.  
  283.             free_cubelist(F2);
  284.             free_cubelist(D2);
  285.         }
  286.     free_cube(cof);
  287.  
  288.     /* Check if any cubes disappeared */
  289.     sf_active(F);
  290.     for(var = 0; var < cube.num_vars; var++)
  291.         if (cube.sparse[var])
  292.             foreach_active_set(F, last, p)
  293.                 if (setp_disjoint(p, cube.var_mask[var]))
  294.                     RESET(p, ACTIVE), F->active_count--;
  295.     if (F->count != F->active_count)
  296.         F = sf_inactive(F);
  297.     return F;
  298. }
  299.